package org.example;

  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


public class Test1 {
    //leetcode 24 两两交换链表中的节点 https://leetcode.cn/problems/swap-nodes-in-pairs/description/

    /**
     * 方法一：递归解决
     * @param prev
     * @param cur
     * @return
     */
    public ListNode swap(ListNode prev,ListNode cur) {
        if (prev == null || cur == null) return prev;
        if (cur.next != null) {
            prev.next = swap(cur.next,cur.next.next);
        }else {
            prev.next = null;
        }
        cur.next = prev;
        return cur;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        return swap(head,head.next);
    }

    /**
     * 方法二：非递归
     * @param head
     * @return
     */
    public ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode phead = new ListNode();
        ListNode prev = head, cur = head.next, nextNode = null, tmp = phead;
        while (cur != null) {
            nextNode = cur.next;
            tmp.next = cur;
            cur.next = prev;
            tmp = prev;
            prev.next = nextNode;
            prev = nextNode;
            if (prev != null) cur = prev.next;
            else cur = null;
        }

        return phead.next;
    }
}
